package com.demo;

import java.util.ArrayList;
import java.util.TreeMap;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        TreeMap<Integer,Integer> treeMap=new TreeMap<>();
        for (int num:nums1){
            if (!treeMap.containsKey(num))
                treeMap.put(num,1);
            else
                treeMap.put(num,treeMap.get(num)+1);

        }
        ArrayList<Integer> res = new ArrayList<>();
        for(int num: nums2){
            if(treeMap.containsKey(num)){
                res.add(num);
                treeMap.put(num, treeMap.get(num) - 1);
                if(treeMap.get(num) == 0)
                    treeMap.remove(num);
            }
        }
        int[] ret = new int[res.size()];
        for(int i = 0 ; i < res.size() ; i ++)
            ret[i] = res.get(i);

        return ret;
    }
}
